int ret = 0;
void fun(vector<int>& nums,int pos,int move){
    if(pos <0 || pos >= nums.size()){
        for(auto e : nums){
            if(e != 0)
                return;
        }
        ret++;
        return;
    }
    if(nums[pos] == 0){
        fun(nums,pos + move,move);
    }else{
        nums[pos]--;
        fun(nums,pos - move,0-move);
        nums[pos]++;
    }
}
class Solution {
public:
    int countValidSelections(vector<int>& nums) {
         ret = 0;
        int n = nums.size();
        for(int i = 0;i < n;i++){
            if(nums[i] == 0)
                fun(nums,i,-1),fun(nums,i,1);
        }
        return ret;
    }
};
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> dp(n + 1);
        for (auto& e : queries) {
            dp[e[0]]++;
            dp[e[1] + 1]--;
        }
        int node = 0;
        // for(auto e :dp){
        //     cout << e << ' ';
        // }
        for (int i = 0; i < n; i++) {
            node += dp[i];
            // cout << node <<' '<< nums[i] << endl;
            if (node < nums[i])
                return false;
        }
        return true;
    }
};
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        bool r = true;
        for(auto e : nums){
            if(e != 0)
                r = false;
        }
        if(r) return 0;
        vector<int> dp(n + 1);
        int left = 0, sum = 0;
        for (int k = 0; k < queries.size(); k++) {
            dp[queries[k][0]] += queries[k][2];
            dp[queries[k][1] + 1] -= queries[k][2];
            if (left <= queries[k][1] && left >= queries[k][0])
                sum += queries[k][2];
            while (left < n && sum >= nums[left]) {
                sum += dp[++left];
            }
            if (left == n)
                return k + 1;
            // cout <<k << ' ' << left << ' ' << sum <<endl;
        }
        return -1;
    }
};